package 七大排序;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author 一哑7
 * @date 2022/03/15 19:33
 * 七大排序
 **/
public class 七大排序 {
    /**
     * 交换元素
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 选择排序单向
     *
     * @param arr //循环遍历数组，i之前是已经排序的，每次从i开始在未排序区间找到最小值与当前位置交换逐个排序
     *            每次从无序区间找到最小值放在无需区间最前端，没经过一轮，一个元素归为，有序加1，无需-1
     *            不稳定
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {//要取最后一个元素，j是i+1，当i是倒数第二个时
                if (arr[j] < arr[min]) {
                    min = j;//暂存索引到min，循环完此层时，min就是最小元素的下标
                    //看清索引下标o
                }
            }
            swap(arr, min, i);
        }
    }

    /**
     * 选择排序双向
     *
     * @param arr 一次循环同时确定左右即最小值与最大值
     */
    public static void selectionSortBothWay(int[] arr) {
        int low = 0;
        int height = arr.length - 1;
        while (low <= height) {
            int min = low;//初始化不是从最大和最小也就是0或length -1 开始，从未排序区间找出最大最小，未排序区间，未排序区间
            int max = low;
            for (int i = low + 1; i <= height; i++) {//在未排序数组中找到最大最小不是全部
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            swap(arr, min, low);
            if (max == low) {//如果一开始的low位置是最大元素的位置，因为经过了最小值归位的交换运算，所以此时最大值的位置在min索引处交换max与min即可
                max = min;
            }
            swap(arr, max, height);
            low += 1;//已经处理过最小的向后移
            height -= 1;
        }
    }

    /**
     * 直接插入排序
     *
     * @param arr 循环数组，每次数组的下一元素插入之前经过的已排序空间
     *            每次从无需区间取第一个插入有序区间的合适位置
     *            稳定
     */
    public static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j >= 1 && arr[j] < arr[j - 1]; j--) {//已排序区间是i之前，i之后取第一个值把他插到排序好的合适位置
                swap(arr, j, j - 1);
            }
//            for (int j = i + 1; j > 0 ; j++) {
//                if (arr[j] < arr[j - 1]){
//                    swap(arr , j , j - 1);
//                }else {
//                    break;
//                }
//            }
        }
    }

    /**
     * 直接插入排序二分优化
     *
     * @param arr 在找插入合适的位置时用二分法查找
     */
    public static void insertionSortBinary(int[] arr) {
        //有序区间[0 , i)
        //无需[i , n]
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];//记录当前位置的索引处的值
            int left = 0;//已经排序好的左右边界
            int right = i;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (val < arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = val;
        }
    }

    /**
     * \
     * 堆排序
     *
     * @param arr 从第一个非叶子节点开始进行元素下沉操作来构造最大堆，构造好之后在依次交换首尾值进行首元素下沉
     */
    public static void heapSort(int[] arr) {
        for (int i = (arr.length - 1 - 1) >> 1; i >= 0; i--) {
            siftDown(arr, i, arr.length - 1);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, 0);
            siftDown(arr, 0, i);
        }
    }

    public static void siftDown(int[] arr, int i, int length) {//对索引元素i进行下沉操作，下沉范围为length
        while (2 * i + 1 < length) {
            int j = 2 * i + 1;
            if (j + 1 < length && arr[j + 1] > arr[j]) {//下沉时j + 1 < length,索引必须是小于长度的不能等于这个东西真的很妙
                j += 1;
            }
            if (arr[i] < arr[j]) {
                swap(arr, i, j);
                i = j;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     *
     * @param arr 循环遍历数组，每次确定最后一个抢位置是未排序区间最大的，有序区间就会相应地减少一个
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwap = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j + 1, j);
                    isSwap = true;
                }
            }
            if (!isSwap) {
                break;
            }
        }
    }

    //希尔排序，缩小增量排序
    //每次取一个gap，将原数组按gap分组，组内插入排序
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            insertionSortGap(arr, gap);
            gap = gap >> 1;
        }
        insertionSort(arr);

    }

    public static void insertionSortGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j >= 0; j = j - gap) {
                swap(arr, j, j - gap);
            }
        }
    }

    public static void mergeSortTwo(int[] arr) {
        for (int i = 1; i < arr.length; i += i) {
            //每次合并的子数组的元素个数
            for (int j = 0; j + i < arr.length; j += 2 * i) {
                //j为每次合并的开始索引
                //元素的起始索引是j每个小数组有i个元素，所以i+ j就是第二个数组也就是带合并数组的右端数组的第一个元素，所以i + j - 1 就mid
                merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));//j + 2 * i - 1同上思路基本一致
            }
        }
    }

    public static void mergeSort(int[] arr) {
        mergeSortResolve(arr, 0, arr.length - 1);
    }

    private static void mergeSortResolve(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        if (r - l <= 15) {
            insertionSort(arr, l, r);
        }
        int mid = l + ((r - l) >> 1);
        mergeSortResolve(arr, l, mid);
        mergeSortResolve(arr, mid + 1, r);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r);
        }
    }

    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {//从l + 1开始防止索引越界
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        //合并
        int[] aux = new int[r - l + 1];
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {
                //左边处理完了，处理右面
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] <= aux[j - l]) {
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    public static void quickSortParticular(int[] arr){
        //不断的做以p为边界的区间分割
        Deque<Integer> stack = new ArrayDeque<>();
        int l = 0 ;
        int r = arr.length - 1 ;
        stack.push(r);
        stack.push(l);
        while (!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right){
                continue;
            }
            int p = partition(arr , left , right);
            stack.push(right);
            stack.push(p + 1);

            stack.push(p - 1);
            stack.push(left);
;        }

    }

    public static void quickSort(int[] arr) {
        partitionHelp(arr, 0, arr.length - 1);
    }

    private static void partitionHelp(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }//random的范围[l , r]r必须>l
        int p = partition(arr, l, r);//以p分区
        partitionHelp(arr, l, p - 1);
        partitionHelp(arr, p + 1, r);
    }

    public static final ThreadLocalRandom random = ThreadLocalRandom.current();

    private static int partition(int[] arr, int l, int r) {
        int p = random.nextInt(l, r);
        swap(arr, l, p);
        int val = arr[l];
        int j = l;//j是比val小的最后一个元素索引，所以j + 1 就是第一个比val 大的元素
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < val) {
                swap(arr, j + 1, i);//变换当前元素位置到比val小的最后索引即第一个比val大的位置
                j++;
            }
        }
        //此时第一个是p，以j为分界[l + 1 , j]为小于val的元素，此时把l 归位即可
        swap(arr, l, j);
        return j;//已经经过转换归为，返回的是判断的值的索
    }

    public static void quickSortTwo(int[] arr){
        partitionHelpTwo(arr , 0 , arr.length - 1);
    }

    private static void partitionHelpTwo(int[] arr, int l, int r) {
        if (r - l <= 15){
            insertionSort(arr , l , r);
            return;
        }
        int p = partitionTwo(arr , l , r);
        partitionHelpTwo(arr , l , p - 1);
        partitionHelpTwo(arr , p + 1 , r);
    }

    private static int partitionTwo(int[] arr, int l, int r) {
        int p = random.nextInt(l , r);
        swap(arr , p , l);
        int val = arr[l];
        int i = l + 1;
        int j = r;
        while (true){
            while (i <= j && arr[i] < val){//左面都是小于，遇到小于不用管
                i ++ ;
            }//左端遇到了第一个大于val的元素索引
            while (i <= j && arr[j] > val){
                j -- ;
            }
            if (i >= j){
                break;
            }
            swap(arr , i , j);
            i ++ ;
            j -- ;//这里减了一次，所以j最后表示的是最后一个<= val的元素
        }
        swap(arr , l , j );
        return j;
    }
    public static void quickSortThree(int[] arr){
        partitionHelpThree(arr , 0 , arr.length - 1);
    }

    private static void partitionHelpThree(int[] arr, int l, int r) {
        if (r - l <= 15){
            insertionSort(arr , l , r);
            return;
        }
        int p = random.nextInt(l , r);
        swap(arr , l , p);
        int val = arr[l];
        int k = l;//[l , k]< 0k是最后一个小于val的元素
        int i = k + 1;//[k + 1 , i] = 0;
        int j = r + 1;//[j , r] > 0;
        while (i < j){
            if (arr[i] < val){
                swap(arr , i , k + 1 );
                i++;
                k++;
            }else if (arr[i] > val){
                swap(arr , i , j - 1);
                j -- ;
            }else {
                i ++ ;
            }
        }
        swap(arr , l , k );
        partitionHelpThree(arr , l ,k -  1);
        partitionHelpThree(arr , j , r );
    }
    public static void quickSortFour(int[] arr){
        partitionFour(arr , 0 , arr.length - 1);
    }

    private static void partitionFour(int[] arr, int l, int r) {

    }

}

